package main.leetcode.clockin.June;

import java.util.Scanner;

/**
 * 10. 正则表达式匹配
 *
 * <p>给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*'
 * 的正则表达式匹配。
 *
 * <p>'.' 匹配任意单个字符 '*' 匹配零个或多个前面的那一个元素 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
 *
 * <p>说明: s 可能为空，且只包含从 a-z 的小写字母。 p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
 *
 * <p>示例 1: 输入: s = "aa" p = "a" 输出: false 解释: "a" 无法匹配 "aa" 整个字符串。
 *
 * <p>示例 2: 输入: s = "aa" p = "a*" 输出: true 解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串
 * "aa" 可被视为 'a' 重复了一次。
 *
 * <p>示例 3: 输入: s = "ab" p = ".*" 输出: true 解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
 *
 * <p>示例 4: 输入: s = "aab" p = "c*a*b" 输出: true 解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串
 * "aab"。
 *
 * <p>示例 5: 输入: s = "mississippi" p = "mis*is*p*." 输出: false
 */
public class day20 {

    public static void main(String[] args) {
        System.out.println(new day20().isMatch("aab", "c*a*b"));
        System.out.println(new day20().isMatch("mississippi", "mis*is*p*."));
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            System.out.println(a + b);
        }
    }

    /** 回溯 + 记忆化技术 */
    public boolean isMatch1(String s, String p) {
        int[][] memo = new int[s.length() + 1][p.length() + 1];
        return memorize(memo, s, 0, p, 0);
    }

    private boolean memorize(int[][] memo, String s, int i, String p, int j) {
        if (j >= p.length()) {
            return i >= s.length();
        }
        if (memo[i][j] > 0) {
            return memo[i][j] == 1;
        }
        boolean firstMatch = i < s.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
        boolean res;
        if (j < p.length() - 1 && p.charAt(j + 1) == '*') {
            res = memorize(memo, s, i, p, j + 2) || firstMatch && memorize(memo, s, i + 1, p, j);
        } else {
            res = firstMatch && memorize(memo, s, i + 1, p, j + 1);
        }
        memo[i][j] = res ? 1 : 2;
        return res;
    }

    /** 动态规划 */
    public boolean isMatch(String s, String p) {
        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
        // s为空，p为空
        dp[0][0] = true;
        // s为空，p第二个为*
        // 比如，s = '', p = 'a*'
        for (int j = 2; j <= p.length(); ++j) {
            dp[0][j] = p.charAt(j - 1) == '*' && dp[0][j - 2];
        }

        for (int i = 0; i < s.length(); ++i) {
            for (int j = 0; j < p.length(); ++j) {
                if (p.charAt(j) == '*') {
                    dp[i + 1][j + 1] =
                            dp[i + 1][j - 1] // s匹配p的去掉*这部分的前一个字符
                                    || dp[i][j + 1]
                                            && (s.charAt(i) == p.charAt(j - 1)
                                                    || p.charAt(j - 1) == '.'); // 匹配*前的重复
                } else {
                    dp[i + 1][j + 1] =
                            dp[i][j] && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
                }
            }
        }
        return dp[s.length()][p.length()];
    }
}
